// 2025/11/16
// 买卖股票的最佳时机4

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size(), dpsize = 2 * k + 1;
        vector<int> dp(dpsize, 0);
        for(int i = 1; i < dpsize; i += 2)
        {
            dp[i] = -prices[0];
        }
        for(int i = 1; i < n; i++)
        {
            for(int j = dpsize - 1; j > 0; j -= 2)
            {
                dp[j] = max(dp[j], dp[j - 1] + prices[i]);
                dp[j - 1] = max(dp[j - 1], dp[j - 2] - prices[i]);
            }
        }
        return dp[dpsize - 1];
    }
};